#pragma once
#pragma once
#include <iostream>
#include <assert.h>
#include <time.h>
using namespace std;


enum Color      // 记录红黑树节点颜色的枚举类型
{
	RED,
	BLACK
};

template<class T1, class T2>
struct RBTreeNode
{
	pair<T1, T2> _data;
	struct RBTreeNode<T1, T2>* _left;
	struct RBTreeNode<T1, T2>* _right;
	struct RBTreeNode<T1, T2>* _parent;   // 存的是当前节点的父节点
	int col;

	RBTreeNode(const pair<T1, T2>& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, col(RED)
		, _parent(nullptr)
	{}
};

template<class T1, class T2>
class RBTree
{
	typedef struct RBTreeNode<T1, T2> Node;
public:
	RBTree() = default;

	// 拷贝构造 (深拷贝)
	RBTree(const RBTree& x)
	{
		_root = _RBTreeConstruct(x._root);
	}

	bool Insert(const pair<T1, T2>& x)
	{
		if (_root == nullptr)       // 第一次插入节点 根节点是黑色的
		{
			_root = new Node(x);
			_root->col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data.first < x.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_data.first > x.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				// 走到else说明搜索二叉树里面有这个值，所以就不用插入
				return false;
			}
		}
		if (parent->_left == cur && parent->_data.first > x.first)  // 确定插入的值在哪边
		{
			parent->_left = new Node(x);
			parent->_left->_parent = parent;
			cur = parent->_left;
		}
		else
		{
			parent->_right = new Node(x);
			parent->_right->_parent = parent;
			cur = parent->_right;
		}
		while (parent && parent->col == RED)                    // 如果插入的值的父节点是红色 说明就需要调整
		{                                             // 并且此时肯定存在祖父节点 因为根节点必须为红色
			Node* grandfather = parent->_parent;      // 通过祖父节点确定叔叔的位置
			Node* uncle = nullptr;
			if (grandfather->_left == parent)
				uncle = grandfather->_right;
			else
				uncle = grandfather->_left;

			if (uncle && uncle->col == RED)           // 情况一  叔叔存在并且为红色
			{
				parent->col = uncle->col = BLACK;
				grandfather->col = RED;
				// 节点继续向上更新
				cur = grandfather;
				parent = cur->_parent;
			}
			else if ((uncle && uncle->col == BLACK) || uncle == nullptr)    // 情况二 叔叔存在且为黑色 或者叔叔不存在
			{
				if (grandfather->_left == parent && parent->_left == cur)
				{
					RotateR(grandfather);
					parent->col = BLACK;
					grandfather->col = RED;
					break;
				}
				else if (grandfather->_right == parent && parent->_right == cur)
				{
					RotateL(grandfather);
					parent->col = BLACK;
					grandfather->col = RED;
					break;
				}
				else if (grandfather->_left == parent && parent->_right == cur)
				{
					RotateL(parent);
					parent = grandfather->_left;
					cur = parent->_left;
				}
				else if (grandfather->_right == parent && parent->_left == cur)
				{
					RotateR(parent);
					parent = grandfather->_right;
					cur = parent->_right;
				}
				else
					assert(false);
			}
			else
				assert(false);
			_root->col = BLACK;
			
		}
		return true;
	}

	Node* Find(const T1& x)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_data.first < x)
			{
				cur = cur->_right;
			}
			else if (cur->_data.first > x)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	bool erase(const T1& x)
	{
		// 当只有一个根节点是特殊处理
		if (_root->_left == nullptr && _root->_right == nullptr)
		{
			if (_root->_data.first == x)
			{
				delete _root;
				_root = nullptr;
				return true;
			}
			else
				return false;
		}
		// 删除有两种情况
		// 1、删除的节点只有一个或者没有子节点
		// 2、删除的节点有两个节点
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			// 第一种情况
			if (cur->_data.first > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_data.first < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				// 处理的特殊情况 根节点是需要消除的节点 并且只有一个子节点
				if (cur == _root && cur->_left == nullptr)
				{
					_root = _root->_right;
					delete cur;
					return true;
				}
				if (cur == _root && cur->_right == nullptr)
				{
					_root = _root->_left;
					delete cur;
					return true;
				}
				int flag = 0;
				if (parent->_right == cur && cur->_left == nullptr)
				{
					parent->_right = cur->_right;
					flag = 1;
				}
				if (parent->_left == cur && cur->_left == nullptr)
				{
					parent->_left = cur->_right;
					flag = 1;
				}
				if (parent->_right == cur && cur->_right == nullptr)
				{
					parent->_right = cur->_left;
					flag = 1;
				}
				if (parent->_left == cur && cur->_right == nullptr)
				{
					parent->_left = cur->_left;
					flag = 1;
				}
				if (flag == 1)
				{
					delete cur;
					return true;
				}
				break;
			}
		}
		// 如果是正常情况下退出循环，说明没有找到要删除的数据
		if (cur == nullptr)
			return false;
		// 第二种情况
		// 可以选择在左边找一个最大值，或者在右边找一个最小值来替代删除的元素
		// 这里实现的是从右边找最小的
		Node* pt = nullptr;
		Node* rt = cur->_right;
		if (rt->_left == nullptr)
		{
			// 说明这个rt的节点就是右边最小的节点
			swap(rt->_data, cur->_data);
			cur->_right = rt->_right;
			delete rt;
			return true;
		}
		// 走到这块说明rt不是右边最小的节点
		while (rt->_left)
		{
			pt = rt;
			rt = rt->_left;
		}
		swap(rt->_data, cur->_data);
		delete rt;
		pt->_left = nullptr;
		return true;

	}


	// 查找二叉树的中序遍历刚好是顺序排序
	void InOrder()
	{
		// 中序遍历需要递归来解决，所以这个 _root 不好传 如果直接用_root 的话 _root 就会被改变
		Node* cur = _root;
		_InOrder(cur);
		cout << endl;
	}

	~RBTree()
	{
		// 后序删除空间  左 右 根
		_RBTreeDestory(_root);
		_root = nullptr;
	}

	bool IsRBTree()
	{
		Node* root = _root;
		if (_root->col == RED)         // 性质一:根节点是黑色
			return false;

		// 性质二:每条路径上的黑色节点数相同
		int BKNum = 0;
		while (root)                   // 先计算一条路径上的黑色节点
		{
			if (root->col == BLACK)
				BKNum++;
			root = root->_left;
		}

		// 性质三:红色节点不能连续出现

		return __IsRBTree(_root, BKNum);
	}

	int Size()
	{
		return _size(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

private:

	bool __IsRBTree(Node* root, int k)
	{
		// 前序遍历判断黑色元素个数
		if (root == nullptr)
			return k == 0;

		if (root->col == BLACK)
			k--;

		if (root->col == RED)                // 如果此节点是红色，那他的父节点就不能为红色
		{
			if (root->_parent->col == RED)
				return false;
		}

		__IsRBTree(root->_left,k);
		__IsRBTree(root->_right,k);
	}

	//bool _IsRBTree(Node* root)
	//{
	//	if (root == nullptr)
	//		return true;

	//	if (root->col == RED)                // 如果此节点是红色，那他的父节点就不能为红色
	//	{
	//		if (root->_parent->col == RED)
	//			return false;
	//	}

	//	return _IsRBTree(root->_left) && _IsRBTree(root->_right);
	//}

	int _size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _size(root->_left) + _size(root->_right) + 1;
	}

	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

	}

	void RotateL(Node* parent)
	{
		Node* parent_Parent = parent->_parent;           // 记录此时根节点的父节点 为后面判断是子树还是根做准备
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		// 左单旋的操作 连接起来节点 并且改变父节点
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

		if (parent_Parent == nullptr)                    // 说明这个节点就为根节点
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else                                             // 说明这个节点只是一个子树的节点
		{
			if (parent_Parent->_left == parent)
				parent_Parent->_left = subR;
			else
				parent_Parent->_right = subR;
			subR->_parent = parent_Parent;
		}

	}

	void RotateR(Node* parent)
	{
		Node* parent_Parent = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;

		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;


		if (parent_Parent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent_Parent->_left == parent)
				parent_Parent->_left = subL;
			else
				parent_Parent->_right = subL;
			subL->_parent = parent_Parent;
		}

	}


	void _RBTreeDestory(Node* root)
	{
		if (root == nullptr)
			return;
		_RBTreeDestory(root->_left);
		_RBTreeDestory(root->_right);
		delete root;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_data.first << ":" << root->_data.second << endl;
		_InOrder(root->_right);
	}


	Node* _RBTreeConstruct(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		// 这里深拷贝需要用到前序遍历   根 左 右
		Node* newnode = new Node(root->_data);
		newnode->bf = root->bf;
		newnode->_left = _RBTreeConstruct(root->_left);
		newnode->_right = _RBTreeConstruct(root->_right);

		return newnode;
	}

private:
	Node* _root = nullptr;
};